package linear.queue.impl;

import linear.queue.Queue;

import java.util.Iterator;

/**
 * 队列
 * @author caasi
 * @since 2022-01-22 15:06:35
 */
public class QueueImpl<E> implements Queue<E> {

    //指向队列的出口，链表的第一个元素
    private Node<E> first;

    //指向队列的入口，链表的最后一个元素
    private Node<E> last;

    private int size;

    public QueueImpl() {
        first = last = null;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void enqueue(E e) {
        Node<E> newNode = new Node<>(e, null);
        if (last != null)
            last.next = newNode;
        last = newNode;
        if (first == null)
            first = last;
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty())
            return null;
        Node<E> node = first;
        first = first.next;
        if (first == null)
            last = first;
        size--;
        return node.e;
    }

    @Override
    public Iterator<E> iterator() {
        return new QueueIterator();
    }

    private class QueueIterator implements Iterator<E> {

        private Node<E> node;
        private int cursor;


        public QueueIterator() {
            node = first;
            cursor = 0;
        }

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public E next() {
            Node<E> e = node;
            node = node.next;
            cursor++;
            return e.e;
        }
    }

    private class Node<E> {

        private Node<E> next;

        private E e;

        public Node(E e, Node<E> next) {
            this.next = next;
            this.e = e;
        }
    }

}
